using System;
using System.Collections.Generic;
using System.Text;

namespace COME342.CollisionResolution.BinaryTree
{
    public class BinaryCollisionResolutionTree<T> : BinaryTreeTX<T, BinaryCollisionResolutionTree<T>>
    {
        public int leftInc;
        public int rightInc;

        public new BinaryCollisionResolutionTree<T> left;
        public new BinaryCollisionResolutionTree<T> right;
        public new BinaryCollisionResolutionTree<T> parent;
        public T givenId;


        public BinaryCollisionResolutionTree(T id, T data, int leftInc, int rightInc)
        {
            this.data = data;
            this.leftInc = leftInc;
            this.rightInc = rightInc;
            this.givenId = id;
        }

        public BinaryCollisionResolutionTree():base()
        {
            
        }

        public void AddToLeft(T id, T data, int leftInc, int rightInc)
        {
            if (left != null)
                throw new ArgumentException("Left subtree is not null. Can not insert.");
            left = new BinaryCollisionResolutionTree<T>(id, data, leftInc, rightInc);
            left.parent = this;
        }

        public void AddToRight(T id, T data, int leftInc, int rightInc)
        {
            if (right != null)
                throw new ArgumentException("Right subtree is not null. Can not insert.");
            right = new BinaryCollisionResolutionTree<T>(id, data, leftInc, rightInc);
            right.parent = this;
        }

        public override string ToString()
        {
            return "Id: " + givenId.ToString() + " Data: " + data.ToString() + " L:" + (left == null ? "-" : left.data.ToString()) + " R:" + (right == null ? "-" : right.data.ToString());
        }

        public new bool IsRoot()
        {
            return parent == null;
        }

        public new BinaryCollisionResolutionTree<T> GetRoot()
        {
            BinaryCollisionResolutionTree<T> bt;
            bt = this;
            while (!bt.IsRoot())
                bt = bt.parent;
            return bt;
        }

        public new bool IsLeftEmpty()
        {
            return left == null;
        }

        public new bool IsRightEmpty()
        {
            return right == null;
        }
    }

    public class BinaryTreeTX<T, X>
    {
        public BinaryTreeTX<T, X> left = null;
        public BinaryTreeTX<T, X> right = null;
        public BinaryTreeTX<T, X> parent = null;
        public T data;        

        public BinaryTreeTX(T data)
        {
            this.data = data;
        }

        public BinaryTreeTX()
        {
        }

        public bool IsRoot()
        {
            return parent == null;
        }

        public BinaryTreeTX<T, X> GetRoot()
        {
            BinaryTreeTX<T, X> bt;
            bt = this;
            while (!bt.IsRoot())
                bt = bt.parent;
            return bt;
        }

        public bool IsLeaf()
        {
            return left == null && right == null;
        }

        public bool IsLeftEmpty()
        {
            return left == null;
        }

        public bool IsRightEmpty()
        {
            return right == null;
        }

        private void PreorderTraverse(ref List<T> ret)
        {
            ret.Add(data);
            if (left != null)
                left.PreorderTraverse(ref ret);
            if (right != null)
                right.PreorderTraverse(ref ret);
        }

        public List<T> PreorderTraverse()
        {
            List<T> ret = new List<T>();
            PreorderTraverse(ref ret);
            return ret;
        }

        public void AddToLeft(T data)
        {
            if (left != null)
                throw new ArgumentException("Left subtree is not null. Can not insert.");
            left = new BinaryTreeTX<T, X>(data);
            left.parent = this;
        }

        public void AddToRight(T data)
        {
            if (right != null)
                throw new ArgumentException("Right subtree is not null. Can not insert.");
            right = new BinaryTreeTX<T, X>(data);
            right.parent = this;
        }

        public void RemoveLeftLeaf()
        {
            if (left == null)
                throw new ArgumentException("Left subtree is null. Can not remove it.");
            if (!left.IsLeaf())
                throw new ArgumentException("Left subtree is not a leaf. Can not remove it with this method.");
            left = null;
        }

        public void RemoveRightLeaf()
        {
            if (right == null)
                throw new ArgumentException("Right subtree is null. Can not remove it.");
            if (!right.IsLeaf())
                throw new ArgumentException("Right subtree is not a leaf. Can not remove it with this method.");
            right = null;
        }

        public void RemoveLeftSubtree()
        {
            left = null;
        }

        public void RemoveRightSubtree()
        {
            right = null;
        }

        public override string  ToString()
        {
            return "Data: " + data.ToString() + " L:" + (left == null ? "-" : left.data.ToString()) + " R:" + (right == null ? "-" : right.data.ToString());
        }

    }

    public class BinaryTreeLisch<T> where T : ILischDataRow
    {
        int mod;

        private int Hash(int x) { return x % mod; }
        private int IncrementingF(int key) { return key / mod % mod; }

        LischTable<T> hashTable;

        public BinaryTreeLisch(int mod)
        {
            this.mod = mod;
            hashTable = new LischTable<T>(mod);
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder(mod);
            
            int i = 0;
            
            foreach (LischTableEntry<T> ihte in hashTable)
            {
                sb.Append(i++.ToString());
                sb.Append("\t");
                sb.AppendLine(ihte == null ? "" : ihte.ToString());
            }
            return sb.ToString();
        }

        public int Insert(T data)
        {
            int hash = data.GetId() % mod;
            int id = data.GetId();
            int oldId = id;

            if(!hashTable.IsColliding(data))
                return hashTable.InsertAt(hash, data);

            int leftInc = IncrementingF(id);
            int rightInc = IncrementingF(hashTable[hash].data.GetId());

            BinaryCollisionResolutionTree<int> bt = new BinaryCollisionResolutionTree<int>();

            Queue<BinaryCollisionResolutionTree<int>> breadth = new Queue<BinaryCollisionResolutionTree<int>>();

            breadth.Enqueue(new BinaryCollisionResolutionTree<int>(Hash(hashTable[hash].data.GetId()), hashTable[hash].data.GetId(), leftInc, rightInc));

            while (breadth.Count > 0)
            {
                bt = breadth.Dequeue();

                hash = bt.givenId;
                id = bt.data;

                leftInc = bt.leftInc;
                rightInc = bt.rightInc;

                if (hashTable[hash + leftInc] == null && bt.IsLeftEmpty())
                {
                    bt.AddToLeft(Hash(hash + leftInc), hash + leftInc, IncrementingF(id), IncrementingF(hashTable[hash].data.GetId())); //rightinc leftinc not important
                    return hashTable.ApplyBinaryTree(bt.left, data);   //hashTable.InsertAt(hash + IncrementingF(id), data);
                }

                if (hashTable[hash + rightInc] == null && bt.IsRightEmpty())
                {
                    bt.AddToRight(Hash(hash + rightInc), hash + rightInc, IncrementingF(id), 0); //rightinc leftinc not important
                    return hashTable.ApplyBinaryTree(bt.right, data);
                }

                if (hashTable[hash + leftInc] != null)
                {
                    bt.AddToLeft(Hash(hash + leftInc), hashTable[hash + leftInc].data.GetId(), leftInc, IncrementingF(hashTable[hash + leftInc].data.GetId()));
                }

                if (hashTable[hash + rightInc] != null)
                {
                    bt.AddToRight(Hash(hash + rightInc), hashTable[hash + rightInc].data.GetId(), IncrementingF(id), IncrementingF(hashTable[hash + rightInc].data.GetId()));
                }

                if (bt.left != null)
                    breadth.Enqueue(bt.left);
                if (bt.right != null)
                    breadth.Enqueue(bt.right);

                oldId = bt.data;
            }

            return -1;
        }

    }
}
